//
// Description: 343. 整数拆分
// Created by Loading on 2022/7/10.
//

#include <bits/stdc++.h>

using namespace std;

int integerBreak(int n) {
    // dp[i] 表示整数 i 拆分成至少两个数后，最大乘积
    vector<int> dp(n + 1);

    for (int i = 2; i < n + 1; ++i) {
        for (int j = 1; j < i; ++j) {
            // 必须拆分成至少两个数，i - j 可以不继续拆分
            dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
        }
    }

    return dp[n];
}

int main() {
    int n = 50;

    int res = integerBreak(n);

    cout << res << endl;

    return 0;
}
